\documentclass[11pt,twoside,a4paper]{article}

\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
%\usepackage{algorithmic}
%\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_{K}}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\Nm}{\mathcal{N}_{\K/\Q}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{Travaux réalisés}
\author{Jean-Fran\c{c}ois Biasse \\
biasse@lix.polytechnique.fr}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières



\section{Introduction}

J'ai effectué des travaux de recherche en théorie algorithmique des nombres et en calcul formel. Je 
me suis aussi intéressé aux applications de ces disciplines à la cryptologie et à la théorie des 
codes.
 
Durant ma thèse effectuée à l'École Polytechnique sous la direction d'Andreas Enge, je me suis focalisé 
sur le calcul du groupe de classes d'idéaux et du groupe des unités d'un corps de nombres. C'est une tâche majeure 
en théorie algorithmique des nombres, intervenant notamment lors de la résolution d'équations 
Diopthantiennes. J'ai aussi appliqué certains résultats au calcul du logarithme discret et au calcul 
d'infrastructure dans les corps de nombres quadratiques, faisant ainsi le lien entre ce domaine et 
la cryptologie.

J'ai ensuite effectué un premier postdoc au département de mathématiques de l'université de Sydney dans 
le groupe de développement du logiciel de calcul formel Magma. J'ai eu l'opportunité d'approfondir les 
sujets de ma thèse, en généralisant les méthodes utilisées pour le calcul du groupe de classes de corps 
quadratiques aux corps de nombres de degré arbitraire. Les algorithmes que j'ai décris sont inspirés du crible 
algébrique qui est le meilleur algorithme de factorisation de grands entiers. 

Lors de mon deuxième postdoc, débuté en avril 2011 à l'université de Calgary, j'ai souhaité élargir 
mes domaines de recherche. Je me suis ainsi tourné vers le calcul formel et les mises sous forme canonique 
de matrices. Je me suis tout d'abord intéressé aux matrices sur $\Z$, et en particulier à la forme normale 
de Hermite qui joue un rôle particulier lors du calcul du groupe de classes d'idéaux d'un corps de nombres. 
J'ai ensuite généralisé des résultats obtenus sur $\Z$ aux modules sur l'anneau des entiers $\OK$ d'un corps
de nombres $K$. La mise sous forme de Hermite d'une base d'un $\OK$-module a des applications en cryptologie
basées sur les réseaux. J'ai aussi eu l'occasion d'appliquer ces résultats à la théorie des codes, et plus 
particulièrement au décodage en liste de codes basés sur les corps de nombres. 
%permet notamment d'exhiber des arguments numériques en faveur de conjectures ouvertes comme les heuristiques de Cohen-Lenstra~\cite{lenstra_heuristic} sur le groupe de classes d'un corps de nombres quadratiques, les bornes de Littlewood~\cite{littlewood} sur $L(1,\chi)$, ou encore la borne de Bach~\cite{bach} sur la borne minimale $B$ assurant que les idéaux de norme bornée par $B$ engendrent le groupe de classes d'idéaux. Ces méthodes servent aussi à la résolution d'équations diophantiennes : par exemple, le calcul de l'unité fondamentale d'un corps quadratique réel permet le calcul des solutions de l'équation de Pell
%$$T^2 - \Delta U^2 = 1,\ \ T,U\in\Z,$$ 
%associée au discriminant $\Delta$ du corps en question (voir \cite{pell_book}). D'autres équations diophantiennes telles que l'équation de Sch\"{a}ffer
%$$y^2=1^k+2^k+\hdots + (x-1)^k,\ \ k\geq 2,$$ 
%se résolvent à partir de l'équation de Pell~\cite{shaffer}, qui est elle-même un cas particulier des équations aux normes de la forme
%$$\mathcal{N}(\alpha) = 1.$$

%Le calcul de la structure de groupes tels que le groupe de classes d'idéaux d'un corps de nombres est intimement lié aux algorithmes de résolution du logarithme discret, qui est un problème de théorie des nombres à la base de nombreux cryptosystèmes à clef publique. Les stratégies employées pour résoudre ce problème dans le groupe de classes d'idéaux sont les même que pour les corps finis et les jacobiennes de courbes hyperelliptiques, ce qui rend son étude intéressante d'un point de vue cryptographique.

\section{Théorie algorithmique des nombres}

Le calcul du groupe de classes d'idéaux $\Cl(\OK)$ d'un corps de nombres $K$ permet notamment d'exhiber des arguments numériques 
en faveur de conjectures ouvertes comme les heuristiques de Cohen-Lenstra~\cite{lenstra_heuristic} sur le groupe de classes d'idéaux 
d'un corps de nombres quadratiques, les bornes de Littlewood~\cite{littlewood} sur $L(1,\chi)$, ou encore la borne de 
Bach~\cite{bach} sur le plus petit entier $B$ tel que les idéaux de norme bornée par $B$ engendrent le groupe de classes 
d'idéaux. Ces méthodes servent aussi à la résolution d'équations diophantiennes : par exemple, le calcul de l'unité 
fondamentale d'un corps quadratique réel permet le calcul des solutions de l'équation de Pell
$$T^2 - \Delta U^2 = 1,\ \ T,U\in\Z,$$ 
associée au discriminant $\Delta$ du corps en question (voir \cite{pell_book}). D'autres équations diophantiennes telles 
que l'équation de Sch\"{a}ffer
$$y^2=1^k+2^k+\hdots + (x-1)^k,\ \ k\geq 2,$$ 
se résolvent à partir de l'équation de Pell~\cite{shaffer}, qui est elle-même un cas particulier des équations aux normes de 
la forme
$$\mathcal{N}(\alpha) = 1.$$

\subsection{Calculs pratiques dans le cas quadratique}

L'algorithme du calcul le plus efficace à ce jour du groupe de classes d'idéaux $\Cl(\OK)$ d'un corps quadratique $K$ a été décrit 
par Hafner et McCurley~\cite{hafner}. Il a ensuite été considérablement amélioré par l'emploi de techniques de crible empruntées 
à la factorisation. Ainsi, l'état de l'art était dû à Jacobson qui a adapté avec succès le \og Multiple Polynomial Quadratic 
Sieve\fg (MPQS) et le \og Self Initialization Quadratic Sieve\fg (SIQS) afin d'accélérer la phase de recherche 
de relations . Outre l'amélioration des temps de calcul, ces méthodes ont permi le calcul du groupe de classes d'idéaux et 
du régulateur 
de corps quadratiques de discriminant ayant 90 chiffres décimaux dans le cas imaginaire et 100 chiffres décimaux dans le cas réel.

J'ai proposé des améliorations à l'algorithme de Jacobson basé sur le SIQS. J'ai en particulier fait appel à la variation des grands 
premiers~\cite{Lenstra2LP}, aux méthodes méthodes d'élimination gaussiennes structurées~\cite{cavallar} ainsi qu'aux tests de 
friabilité simultanés dûs à Bernstein~\cite{bernstein}. Ces techniques se sont révélées efficaces. Elles permettent 
une amélioration d'au moins un facteur 4 sur la même plateforme par rapport au SIQS classique de Jacobson. De même, j'ai réalisé 
le calcul du groupe de classes d'idéaux et du régulateur pour des corps de nombres ayant un discriminant de 110 chiffres décimaux 
dans le 
cas imaginaire comme dans le cas réel. Les améliorations concernant le cas imaginaire sont décrites dans~\cite{biasse_quad}, 
tandis que celles concernant le cas réel, qui ont été réalisées en collaboration avec Jacobson à l'université de Calgary, se 
trouvent dans~\cite{BiaJac10}.

Mes travaux sur les corps quadratiques ont été distribués via le logiciel de calcul formel MAGMA~\cite{magma}. 


%Pour améliorer la phase de recherche de relations, j'ai pris comme point de départ les méthodes de crible utilisées par Jacobson 
%auxquelles j'ai ajouté l'utilisation d'autres techniques d'optimisations connues dans le cadre de la factorisation. J'ai ainsi 
%utilisé les variations des grands premiers~\cite{Lenstra2LP}, des méthodes d'élimination gaussiennes structurées~\cite{cavallar} 
%ainsi que des tests de friabilité simultanés~\cite{bernstein}.

%\`{A} l'instar de la factorisation, le calcul du groupe de classes et du régulateur comporte une phase d'algèbre linéaire. 
%Celle-ci se résume à calculer la forme normale de Smith (SNF) de la matrice des relations afin d'en extraire la structure du 
%goupe de classes, et à calculer des éléments du noyau de la matrice des relations pour obtenir le régulateur et l'unité fondamentale. Je me suis intéressé à des méthodes alternatives de calcul de ces objets à base de résolution de systèmes linéaires diophantiens. Des algorithmes ont été décrits de manière théorique par Vollmer~\cite{vollmer,Vreg} sans toutefois avoir été implantés. J'ai montré que ces algorithmes avaient un impact d'un point de vue pratique par comparaison avec les algorithmes précédemment utilisés.

%Les amélioration pratiques pour le calcul du groupe de classes que j'ai proposées se sont révélées efficaces. Elles permettent 
%une amélioration d'au moins un facteur 4 sur la même plateforme par rapport au SIQS classique de Jacobson. De même, j'ai réalisé 
%le calcul du groupe de classe et du régulateur pour des corps de nombres ayant un discriminant de 110 chiffres décimaux dans le 
%cas imaginaire comme dans le cas réel. Les améliorations concernant le cas imaginaires sont décrites dans~\cite{biasse_quad}, 
%tandis que celles concernant le cas réel, qui ont été réalisées en collaboration avec Jacobson à l'université de Calgary, se 
%trouvent dans~\cite{BiaJac10}.



%Les travaux décrits précédemment ont tout d'abord été implantés pour les besoins des publications en C++ à partir des bibliothèques GMP et NTL pour l'arithmétique multiprécision, ainsi que Linbox et IML pour l'algèbre linéaire dense. Il sont depuis distribués via le logiciel de calcul formel MAGMA. 
%préciser à la fin comment c'est distribué
\subsection{Calculs pratiques en degré arbitraire}

Les algorithmes décrits dans~\cite{biasseL13} sont basés sur le crible algébrique qui s'est révélé être efficace dans 
la pratique pour la factorisation d'entiers de taille record. Afin d'étendre l'utilisation du crible au calcul du groupe 
de classes d'idéaux, du régulateur et d'un système fondamental d'unités d'un corps de nombres de degré arbitraire, j'ai 
implanté en collaboration avec Fieker à l'université de Sydney une recherche de relations similaire à celle du crible algébrique. 
Cette méthode tire parti des améliorations les plus récentes du crible algébrique telles que le \og lattice sieving\fg et le 
\og special-$q$\fg. Cette avancée permet une amélioration significative des 
performances par rapport à la stratégie décrite dans~\cite{Buchmann}, tout particulièrement pour les petits degrés.

Afin de réduire la précision nécessaire au calcul du régulateur, j'ai employé, en collaboration avec Fieker, une méthode basée 
sur des approximations $p$-adiques plutôt que des approximations à virgule flottante ou fixe. L'emploi des $p$-adiques 
permet notamment de ne pas subir de perte de précision à chaque manipulation d'une approximation rationnelle d'une valeur réelle. 
Cette stratégie s'est révélée très efficace.

Les améliorations concernant les corps de nombres de degré arbitraire seront, à l'instar du cas quadratique, distribués via le 
logiciel de calcul formel MAGMA~\cite{magma}.

\subsection{Résultats théoriques}

Jusqu'à présent, la meilleure complexité (heuristique) connue pour le calcul du groupe de classes d'idéaux, du régulateur et 
d'un système d'unités fondamentales dans un corps de nombre de dimension fixée $n$ et de discriminant $\Delta$ était en 
$L_\Delta(1/2 , O(1))$, où la fonction sous-exponentielle $L$ est définie par
$$L_\Delta ( \alpha , \beta ) := e^{\beta (\log|\Delta|)^{1/3}(\log\log|\Delta|)^{2/3}}.$$
Ce résultat, dû à Buchmann~\cite{Buchmann}, est une généralisation de l'approche de Hafner et McCurley~\cite{hafner} qui ont 
traité le cas quadratique. Il ne s'étend pas aux classes de corps de nombres de degré croissant vers l'infini, et ne mentionne 
pas la précision à laquelle le régulateur est calculé.

J'ai décrit~\cite{biasseL13} un algorithme pour le calcul du groupe de classes d'idéaux, du régulateur et d'un système d'unités 
fondamentales dont la complexité heuristique dans certaines classes infinies de corps de nombres est en $L(1/3,O(1))$. 
Cet algorithme est inspiré du travail de Enge et Gaudry~\cite{Enge} dans les jacobiennes de courbes $C_{a,b}$, dérivant lui même 
de l'algorithme du crible algébrique~\cite{NFS} pour la factorisation de grands entiers. Ces classes infinies sont les premières 
pour lesquelles le calcul de ces objets peut se faire en une meilleure complexité que $L(1/2,O(1))$. Dans~\cite{biasseL13}, 
j'ai aussi analysé rigoureusement  la perte de précision engendée par le calcul du régulateur, indispensabe pour garantir la 
précision de l'approximation calculée ainsi que l'exactitude des unités fondamentales. J'ai aussi adapté ces 
résultats~\cite{biasseDLPL13} à la résolution du problème du logarithme discret dans le groupe de classes et du test de 
principalité d'un idéal dans l'ordre maximal d'un corps de nombres, qui peuvent tous deux se résoudre en complexité 
heuristique $L(1/3)$.

\section{Calcul Formel}

Étant donnés un anneau $R$, et un $R$-module de dimension $n$, une tâche essentielle en calcul formel est le calcul de 
$b_1,\cdots,b_n$ jouissant de bonnes propriétés et tels que 
$$M = R b_1 + \cdots + R b_n.$$
Par exemple. dans le cas $R = \Z$, l'algorithme LLL~\cite{LLL} permet de trouver une base de $M$ ayant de courts 
vecteurs, permettant ainsi de faciliter la résolution de la recherche du plus court vecteur dans $M$, ou bien la recherche 
du vecteur le plus proche dans $M$.

\subsection{Forme de Hermite dans $\Z$}

%Tasks such as computing the structure of a finite group, factoring an integer or solving the discrete logarithm problem involve 
%processing matrices of large entries. Depending on the context, these matrices can be over a finite field or over $\Z$, the latter
%being more memory consuming. In particular, the Hermite normal form (HNF) is a lower triangular form used for computing finite 
%group structures and solving the discrete logarithm problem. Very few implementations of HNF algorithms for matrices over $\Z$ are available. The 
%fastest one is indisputably the one implemented by Steel in Magma~\cite{magma}, but it is unfortunately not freely available, nor
%open source or even published. 
La mise sous forme triangulaire d'une matrice intervient souvent dans le contexte de la théorie algorithmique des nombres et de la 
cryptologie. Cela peut s'appliquer à la résolution d'équations, au calcul de la structure d'un groupe fini ou encore 
à la résolution du problème du logarithme discret. En particulier, la forme normale de Hermite (HNF) d'une matrice à coefficients 
dans $\Z$ permet de trouver une base appropriée du $\Z$-module des relations d'un groupe fini. Cette base HNF est utilisable pour 
le calcul de la structure du groupe fini en question, ainsi que la résolution du problème du logarithme discret. Peu 
d'implémentations efficaces d'algorithmes de mise sous forme HNF de matrices sont disponibles, et le plus rapide, distribué via 
le logiciel de calcul formel Magma~\cite{magma} n'est malheureusement ni open source, ni même publié dans la littérature.

%In collaboration with Boyer (University of Grenoble), I am currently filling this void by implementing efficient algorithms in the C++ linear algebra library 
%Linbox~\cite{linbox}. We are implementing the main existing algorithms for computing the HNF of an integer matrix. We are also testing
%new algorithmic ideas that allow to take into account the specificities of the matrices that occur in the context of index calculus. 
%Indeed, these matrices usually have very large dimensions, but also relatively small entries, and a small essential part. These
%specificities are not exploited by the current available algorithms. Our goal is to provide a comparison between the existing 
%algorithms and our improvements and to release our implementation via the open source project linbox.
En collaboration avec l'équipe CASYS du laboratoire Jean Kunzmann à Grenoble, j'ai implanté des algorithmes efficaces permettant 
la mise sous forme HNF d'une matrice sur les entiers. Notre angle d'attaque a été de prendre en compte les spécificités des matrices 
traitées dans les algorithmes de calcul d'index tels que la résolution du logarithme discret ou la recherche de la structure d'un 
groupe. En effet, d'un côté ces matrices peuvent avoir de grandes dimensions, mais de l'autre, elles sont souvent creuses, avec 
des coefficients de petite taille et  leur forme de Hermite a seulement un petite partie non triviale (partie essentielle). Ces 
spécificités ne sont pas exploitées par les algorithmes disponibles à l'heure actuelle. Nous avons diffusé via le projet open 
source Linbox~\cite{linbox} une série d'algorithmes pour le calcul de HNF, dont l'implantation originale d'un algorithme par blocs 
basé sur les idées de Storjohann et al. décrites dans~\cite{JacobsonHNF}.

\subsection{Bases réduites d'un $\OK$-module}

%The construction of a good basis of an $\OK$-module, where $K$ is a number field and $\OK$ its ring of 
%integers, has recently received a growing interest from the cryptographic community. Indeed, $\OK$-modules 
%occur in lattice-based cryptography~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, where 
%cryptosystems rely on the difficulty to find the shortest element of a module, or solving the closest 
%vector problem. The computation of a good basis is crucial for solving these problems, and most of the 
%algorithms for computing a reduced basis of a $\Z$-lattice have an equivalent for $\OK$-modules. However, 
%applying the available tools over $\Z$ to $\OK$-modules would result in the loss of of their structure.
La construction d'une bonne base pour un $\OK$-module où $K$ est un corps de nombres et $\OK$ son anneau des 
entiers a reçu dernièrement un attention considérable de la part de la communauté scientifique. En effet, les 
$\OK$-modules interviennent en cryptographie basée sur les réseaux~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, 
où la sécurité des cryptosystèmes repose sur la difficulté de trouver le vecteur le plus court, ou le vecteur le
plus proche.

%The computation of a Hermite Normal Form (HNF)-basis was generalized to $\OK$-modules by Cohen~\cite[Chap. 1]{cohen2}. 
%His algorithm returns a basis that enjoys similar properties as the HNF of a $\Z$-module. A 
%modular version of this algorithm is conjectured to run in polynomial time, although this statement is not 
%proven (see last remark of~\cite[1.6.1]{cohen2}). In addition, Fieker and Stehl{\'e}'s recent algorithm for computing a 
%sized-reduced basis relies on the conjectured possibility to compute an HNF-basis for an $\OK$-module in polynomial 
%time~\cite[Th. 1]{stehle_fieker_LLL}.
Le calcul de la HNF a été généralisé aux $\OK$-modules par Cohen~\cite[Chap. 1]{cohen2}. Son algorithme retourne une base 
ayant des propriétés similaires à celles de la HNF sur $\Z$. Cohen a conjecturé que la version modulaire de cet algorithme 
avait une complexité polynomiale, mais aucune preuve n'est disponible dans la littérature. De plus, Fieker et Stehl{\'e} ont 
récemment publié un algorithme analogue à l'algorithme LLL pour le calcul d'une base réduite d'un $\OK$-module dont le temps 
de calcul repose sur la polynomialité de l'algorithme de Cohen\cite[Th. 1]{stehle_fieker_LLL}. En collaboration avec Fieker, 
j'ai élaboré une version modifiée de l'algorithme de Cohen dont nous avons analysé la complexité~\cite{pseudo_HNF}. C'est le 
premier algorithme polynomial de calcul de la HNF d'un $\OK$ module. 


\section{Cryptologie et théorie des codes}

\subsection{Stream ciphers}

%During the eSTREAM competition, Bernstein described a family of stream ciphers called 
%Salsa/$i$ (see~\cite{salsa20}), where $i$ denotes
%the number of rounds used. Berstein emphasized the use of 8, 12 and 20 rounds. Crowley~\cite{crowley} was the first to present an 
%attack on Salsa. His differential cryptanalysis was valid for 5 rounds. The same year, I presented, in collaboration with Berbain, 
%Fisher, Meier and Robshaw (FHNW and Orange labs)~\cite{Orange_salsa} an attack valid for 6 and 7 rounds of the stream cipher Salsa. 
%Since then, the best cryptanalysis published on Salsa is valid for 8 rounds~\cite{Salsa_8}. It is therefore safe to say that the 
%family of ciphers Salsa
%represent a strong computational challenge. 
Pendant la compétition eSTREAM, Bernstein a décrit une famille de stream ciphers appelée Salsa/$i$ (voir~\cite{salsa20}), où 
$i$ dénote le nombre de tours utilisés. Bernstein a mis l'accent sur l'usage de 8, 12, 20 tours. Crowley~\cite{crowley} a été le 
premier à présenter une attaque sur la famille de stream ciphers Salsa. Sa cryptanalyse différentielle fonctionne sur 5 tours. La 
même année, j'ai présenté, en collaboration avec Berbain, Fisher, Meier et Robshaw (FHNW et Orange labs)~\cite{Orange_salsa}, une 
attaque valide pour 6 et 7 tours du stream cipher Salsa. Depuis, la meilleure cryptanalyse publiée sur Salsa est valide sur 
8 tours~\cite{Salsa_8}. Salsa est donc bien une famille de stream ciphers intéressante, repoussant les limites des techniques 
de cryptanalyse symétrique.   

\subsection{Logarithme discret}

J'ai réalisé des implantations d'algorithmes pour la résolution du problème du logarithme discret dans le groupe de classes 
d'idéaux d'un ordre quadratique, et de la résolution du problème de principalité d'idéaux dans un ordre quadratique à partir de 
résolution de systèmes linéaires diophantiens. Ces implantations comprenant 
des améliorations pratiques significatives par rapport au précédant étant de l'art, j'ai entrepris, en collaboration avec 
Jacobson et Silvester à l'université de Calgary, une nouvelle étude de la sécurité des cryptosystèmes reposant sur la 
difficulté de ces problèmes dans le cas quadratiques~\cite{BiaJacSil10}. La conclusion de ce projet a été la nécessité de 
relever la taille des clefs par rapport aux précédantes recommantations~\cite{HMiq}.

\subsection{Décodage en liste de codes sur les corps de nombres}
%In his thesis, Guruswami~\cite[Chap. 7]{guruswami_phd} described a general framework for list decoding residue codes. These codes 
%are defined by a ring $R$ and coprime ideals $I_1,\cdots,I_n$. The encryption function is given by
%\[   \left. \begin{array}{cccc}
%      &   R & \longrightarrow  & R/I_1\times \cdots \times R/I_n \\
%    c:&    m & \longmapsto & (m\bmod I_1,\cdots ,m \bmod I_n) \end{array} \right. . \]
%In the case where $R$ is the univariate polynomial ring over a finite field, and the $I_i$ are generated by polynomials $p_i$, the message 
%is transmitted via the evaluation of the $p_i$ at a point, which is precisely the definition of Reed-Solomon codes. This approach 
%allows to unify the decoding of Reed-Solomon codes, their generalization the algebraic-geometric codes~\cite{wasserman}, and the 
%Chinese remainder codes~\cite{guruswami_sudan_soft_CRT} where the message is the residue of an integer modulo a tuple of $n$ prime
%numbers.
Dans sa thèse, Guruswami~\cite[Chap. 7]{guruswami_phd} a décrit une stratégie générale pour décoder en liste des codes à base de 
résidus. Ces codes sont définis par un anneau $R$ et des idéaux premiers entre eux $I_1,\cdots,I_n$. L'encodage est donné par 
\[   \left. \begin{array}{cccc}
      &   R & \longrightarrow  & R/I_1\times \cdots \times R/I_n \\
    c:&    m & \longmapsto & (m\bmod I_1,\cdots ,m \bmod I_n) \end{array} \right. . \]
Dans le cas où $R$ est l'anneau des polynômes à une indéterminée sur un corps fini, et les $I_i$ sont générés par des polynômes 
$p_i := X-\alpha_i$, le message $m$ est transmis via son évaluation en les $\alpha_i$, ce qui est précisément la définition des codes de Reed-Solomon.
Cette approche permet d'unifier le décodage des codes de Reed-Solomon, leur généralisation les codes 
algébriques-géométriques~\cite{wasserman} et les codes CRT~\cite{guruswami_sudan_soft_CRT} pour lesquels le message est une 
collection de résidus modulo un $n$-uplet de nombres premiers.  

%The case where $R$ is the ring of integers of a number field and the $I_i$ are prime ideals $\p_i\subset R$ was studied independantly
%by  Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}. They exhibited classes of number fields with good properties,
%but failed at providing a decoding algorithm. In collaboration with Quintin (\'{E}cole Polytechnique), I described the first polynomial time algorithm for 
%decoding codes based on number fields~\cite{biasse_codes}. We showed that we could achieve the same decryption bounds as for the 
%Chinese Remainder Codes..
Le cas où $R$ est l'anneau des entiers d'un corps de nombres et les $I_i$ sont des idéaux premiers $p_i\subset R$ a été étudié 
indépendamment par Lenstra~\cite{lenstra_nb_fld} et Guruswami~\cite{guruswami_nb_fld}. Ils ont mis en évidence des classes de 
corps de nombres jouissant de bonnes propriétés, mais n'ont pas décrit d'algorithme de décodage. En collaboration avec Quintin, j'ai 
décrit le prmier algorithme polynomial de décodage en liste pour les codes basés sur les corps de nombres~\cite{biasse_codes}. Nous 
avons montré que nous pouvions atteindre la borne de Johnson pour le décodage en liste, ce qui est similaire à l'état de l'art pour 
le cas plus simple des codes CRT.


\bibliography{travaux}

\end{document}